package seqlist;

import java.util.Arrays;

public class DynamicArray {
    // 定义属性
    // elementData就是具体存储元素的数组
    private int[] elementData;
    // 当前动态数组中存储了几个元素
    private int size;

    public DynamicArray() {
        this.elementData = new int[10];
    }

    public DynamicArray(int size) {
        elementData = new int[size];
    }

    /**
     * 在数组头部添加元素
     * @param data
     */
    public void addFirst(int data) {
        // 此时内部小数组已满,需要扩容
        if (size == elementData.length) {
            grow();
        }
        for (int i = size - 1;i >= 0;i --) {
            elementData[i + 1] = elementData[i];
        }
        // 此时index = 0；数组头部空间空出来
        elementData[0] = data;
        size ++;
    }

    /**
     * 在数组的尾部添加元素
     * @param data
     */
    public void addLast(int data) {
        if (size == elementData.length) {
            grow();
        }
        elementData[size] = data;
        size ++;
    }

    /**
     * 在数组的索引index处添加元素
     * @param index
     * @param data
     */
    public void addIndex(int index,int data) {
        // index在插入时，特殊场景
        // index = 0 -> 头插
        // index = size -> 尾插
        // 先判断边界条件 index是否合法
        if (index < 0 || index > size) {
            System.out.println("index非法，无法进行插入");
            return;
        }
        // 判断当前数组是否已满
        if (size == elementData.length) {
            grow();
        }
        // 数据插入
        if (index == 0) {
            addFirst(data);
        }
        if (index == size) {
            addLast(data);
        }else {
            // 在数组的中间位置插入
            for (int i = size - 1; i >= index; i--) {
                elementData[i + 1] = elementData[i];
            }
            // 此时index位置空出
            elementData[index] = data;
            size ++;
        }
    }
    // 内部扩容方法
    private void grow() {
        int oldLength = elementData.length;
        int newLength = oldLength << 1;
        // 将原数组搬移到新数组
        elementData = Arrays.copyOf(elementData,newLength);
    }

    // 取得当前数组长度
    public int getSize() {
        return size;
    }

    /**
     * 将当前动态数组转换为字符串
     * @return
     */
    public String toString() {
        // 每个元素都在elementData数组中存储
        String ret = "[";
        for (int i = 0; i < size; i++) {
            ret += elementData[i];
            if (i != size - 1) {
                ret += ", ";
            }
        }
        ret += "]";
        return ret;
    }

    public int get(int index) {
        if (rangeCheck(index)) {
            return elementData[index];
        }
        return -1;
    }

    /**
     * 判断当前集合中是否包含指定元素data
     * @param data
     * @return
     */
    public boolean contains(int data) {
        for (int i = 0; i < size; i++) {
            if (elementData[i] == data) {
                return true;
            }
        }
        return false;
    }

    public void remove(int index) {
        if (rangeCheck(index)) {
            // 从index位置开始，将之后的元素统一前移一位
            for (int i = index;i < size - 1;i++) {
                elementData[i] = elementData[i + 1];
            }
            size --;
            // 将最后一个元素删除，元素重置为0
            elementData[size] = 0;
        }
    }

    /**
     * 按值删除,删除线性表中所有值等于value的元素
     * @param value
     */
    public void removeValue(int value) {
        for (int i = 0; i < size; i++) {
            while (elementData[i] == value && i < size) {
                // 此时位置i就是待删除的元素下标
                remove(i);
            }
        }
    }


    /**
     * 将指定位置index的元素修改为新值newData
     * @param index
     * @param newData
     * @return 修改前的元素
     */
    public int set(int index,int newData) {
        if (rangeCheck(index)) {
            int oldValue = elementData[index];
            elementData[index] = newData;
            return oldValue;
        }
        return -1;
    }

    /**
     * 校验当前传入的index是否合法(用在查询，设置，删除)
     * @param index
     * @return
     */
    private boolean rangeCheck(int index) {
        if (index < 0 || index >= size) {
            // 错误输出
            System.err.println("当前index非法,index >= 0 && index < size");
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        DynamicArray dynamicArray = new DynamicArray();
        dynamicArray.addLast(2);
        dynamicArray.addLast(2);
        dynamicArray.addLast(2);
        dynamicArray.addLast(2);
        dynamicArray.addLast(1);
        // [3,2,2,2,1]
        System.out.println(dynamicArray);
        dynamicArray.removeValue(2);
        // [3,1]
        System.out.println(dynamicArray);
    }
}
